﻿/*
* @autor: hectorea
* @date: 24/07/12
* @programming interview 7
*/

using System;
using System.Collections.Generic;
using System.Linq;

namespace SecondMaximum
{
    /// <summary>
    /// Programming Interview 7: Write a function to find 2nd maximum number in the given array
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {

            int[] input = { 100, 20, 2, 5, 9, 8, 3, 1, 100, 50, 34, 45, 23, 2, 12, 22, 55, 66, 88, 90, 95, 4, 100 };

            Console.WriteLine("The 2nd maximum number is: {0}", GetSecondWithLinq(input));
            Console.ReadLine();

            Console.WriteLine("The 2nd maximum number is: {0}", GetSecondMaximumFromUnSortedArray(input));
            Console.ReadLine();

            Console.WriteLine("The 2nd maximum number is: {0}", GetSecondMaximumFromOrderedArray(input));
            Console.ReadLine();
        }

        #region [ With Sorting Algortithm ]
        /// <summary>
        /// Return the 2nd maximum value from an unordered array by sorting the input array. 
        /// We can use any sorting algorithm (BubbleSort, Quicksort, MergeSort, etc.).  
        /// For this exercise I'll use Bubblesort due to ease to implement it.
        /// </summary>
        /// <param name="input">Unordered array</param>
        /// <returns>The 2nd maximum value</returns>
        private static int GetSecondMaximumFromOrderedArray(int[] input)
        {
            int[] ordered = BubbleSort(input);

            int second = 0;

            for (int i = 1; i < ordered.Length; i++)
            {
                if (input[i] < input[i - 1])
                {
                    second = input[i];
                    break;
                }
            }

            return second;
        }

        /// <summary>
        /// Order the input array descendant order
        /// </summary>
        /// <param name="input">Unordered aray</param>
        /// <returns>An descendant ordered array</returns>
        private static int[] BubbleSort(int[] input)
        {
            for (int i = 0; i < input.Length; i++)
            {
                for (int j = i; j < input.Length; j++)
                {
                    if (input[i] < input[j])
                    {
                        input[i] ^= input[j];
                        input[j] ^= input[i];
                        input[i] ^= input[j];
                    }
                }
            }

            return input;
        }
        #endregion

        #region [ Without Sorting Algoritm ]
        public static int GetSecondMaximumFromUnSortedArray(int[] input)
        {
            //If we are expecting to get the "2ndMaximum" is correct to have this validation?
            if (input == null || input.Length <= 2)
                throw new ArgumentNullException("The input cannot be null or at least have two values");

            int first = input[0];
            int second = 0;

            for (int i = 1; i < input.Length; i++)
            {
                int current = Convert.ToInt32(input[i]);

                if (current > first)
                {
                    second = first;
                    first = current;
                }
                else if (current > second && current < first)
                {
                    second = current;
                }
            }

            return second;
        }
        #endregion

        #region [ Linq ]
        /// <summary>
        /// Order the array in descending order and then select the distinct values. Once perfomed this actions, 
        /// we select the second element
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        private static int GetSecondWithLinq(int[] input)
        {
            //Due to we only have Distinct values and ther're already ordered in Descending Order, 
            //we can obtain directly the second position that will have the 2nd maximum number
           
            //int second =
            //    input.OrderByDescending(x => x)
            //    .Distinct<int>().Skip(1).First();
           
            List<int> numbers = input.ToList<int>();
            int second = (from number in numbers
                          orderby number descending
                          select number).Distinct().Skip(1).First();

            return second;
        }
        #endregion
    }
}

